For example, it becomes harder for a semiconductor nonvolatile storage medium such as a NAND flash memory to keep a lower cell error ratio as a fine-process is executed for that medium. In the storage device using the NAND flash memory, redundant data for write data from a host is generated using error correction codes, and the data and redundant data are written in the NAND flash memory.
In general, in the error correction codes, as a larger redundant part is set (to decrease an encoding ratio) with respect to an information part, a correction capability is enhanced. However, when a redundant write amount becomes large, a logical capacity where the host can store data becomes smaller with respect to a physical capacity of a storage medium. When the information part and redundant part are allocated in areas in which they cannot be simultaneously accessed, on the medium, a write or read performance lowers. Hence, by allocating the information part and redundant part in an area in which they can be simultaneously accessed, the write and read performances can be enhanced.
As an error correction technique, hierarchization or long coding of error correction codes, a combination of encoder and decoder which enhance a correction capability decided based on probability information, and the like have been proposed.
The hierarchization of codes is a method of generating a plurality of codewords for one information part, providing different error correction capabilities to the respective codewords, and attempting to decode in turn from a codeword which can be decoded quickly. With this hierarchization of codes, a high error correction capability including decoding of a codeword in the last layer can be obtained while maintaining an average read performance. However, redundant parts of all layers are large, and when all these redundant parts are stored in a storage medium, the logical capacity of the storage medium is reduced.
The long coding of codes uses, in general, a property in which a frame including long codewords can set a lower frame error ratio than a frame including short codewords at the same encoding ratio. This is because a probability of concentrating errors in one codeword in a frame, which errors cannot be corrected by that codeword, is lower for a long codeword than a short codeword. However, when a long codeword is set, an error correction capability decided by an encoding ratio is limited. Also, as a codeword becomes longer, a longer decoding time is required, thus impairing the read performance.
A method of enhancing a correction capability of a codeword itself using probability information for respective bits of the codeword is available. However, a read access of the probability information requires a longer time than a normal bit read access, and a decoder requires a larger circuit scale and consumption power.